package chapter01.problem02;

import java.util.Collection;
import java.util.NoSuchElementException;
import java.util.Stack;
/**
 * 第二题：使用两个栈实现队列的功能
 * @param <T>	队列中保存的参数类型
 */
public class QueueComposedBy2Stack<T>{

	private Stack<T> originalData;
	private Stack<T> orderedData;
	private int size;
	
	/**
	 * 构造函数
	 */
	public QueueComposedBy2Stack(){
		originalData = new Stack<T>();
		orderedData = new Stack<T>();
		size=0;
	}
	
	/**
	 * 返回队列的规模
	 * @return	队里的规模
	 */
	public int size() {
		return size;
	}
	
	/**
	 * 队列是否为空
	 * @return	如果为空则返回true，否则返回false
	 */
	public boolean isEmpty() {
		return size ==0;
	}
	
	/**
	 * 是否包含整个集合
	 * @param c 待比较的集合
	 * @return	如果包含c,则返回true，否则返回false 
	 */
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		if(c.size() != orderedData.size()+originalData.size())
			return false;
		for (Object object : c) {
			if(!(originalData.contains(object) || orderedData.contains(object)))
				return false;
		}
		return true;
	}
	/**
	 * 清空队列中的所有元素，调用该方法之后，队列为空
	 */
	public void clear() {
		originalData.clear();
		orderedData.clear();
		size=0;
		
	}
	
	/**
	 * 往队列里面添加元素
	 * @param e 要添加的元素
	 * @return 是否添加成功
	 */
	public boolean add(T e) {
		boolean isSucc = originalData.add(e);
		if(isSucc){
			size++;
		}
		return isSucc;
	}
	
	/**
	 * 往队列里面添加元素
	 * @param e 要添加的元素
	 * @return 是否添加成功
	 */
	public boolean offer(T e) {
		boolean isSucc = originalData.add(e);
		if(isSucc){
			size++;
		}
		return isSucc;
	}
	
	/**
	 * 得到队列的头并从队列中移除，与{@link #poll() poll}的不同在于，如果队列为空，则抛出异常
	 * @return 队列的头
	 * @throws NoSuchElementException 如果队列为空
	 */
	public T remove() throws NoSuchElementException{
		if(!orderedData.isEmpty()){
			size--;
			return orderedData.pop();
		}else if(!originalData.isEmpty()){
			orderStack();
			size--;
			return originalData.pop();
		}else 
			throw new NoSuchElementException("Queue is empty!");
	}
	
	/**
	 * 得到队列的头并从队列中移除，如果队列为空，则返回null
	 * @return 队列的头或者null
	 */
	public T poll() {
		if(!orderedData.isEmpty()){
			size--;
			return orderedData.pop();
		}else if(!originalData.isEmpty()){
			orderStack();
			size--;
			return orderedData.pop();
		}else 
			return null;
	}
	/**
	 * 得到队列的头元素，并不移除头元素，与{@link #peek() peek}的不同在于如果队列为空，则抛出异常
	 * @return 队列的头元素
	 * @throws NoSuchElementException 如果队列为空
	 */
	public T element() {
		if(!orderedData.isEmpty()){
			return orderedData.peek();
		}else if(!originalData.isEmpty()){
			orderStack();
			return orderedData.peek();
		}else 
			throw new NoSuchElementException("Queue is empty!");
	}
	/**
	 * 得到队列的头元素，并不移除头元素，如果队列为空，则返回null
	 * @return	队列的头元素或null
	 */
	public T peek() {
		if(!orderedData.isEmpty()){
			return orderedData.peek();
		}else if(!originalData.isEmpty()){
			orderStack();
			return orderedData.peek();
		}else 
			return null;
	}
	private void orderStack(){
		while(!originalData.isEmpty()){
			orderedData.push(originalData.pop());
		}
	}
	
	public static void main(String[] args) {
		QueueComposedBy2Stack<Integer> queue = new QueueComposedBy2Stack<Integer>();
		System.out.println("queue.isEmpty: " + queue.isEmpty());
		queue.add(1);
		queue.add(2);
		queue.add(3);
		queue.add(4);
		System.out.println("queue.peek()"+queue.peek());
		System.out.println("queue.poll()"+queue.poll());
		queue.add(5);
		System.out.println("queue.peek()"+queue.peek());
		System.out.println("queue.poll()"+queue.poll());
		System.out.println("queue.poll()"+queue.poll());
		System.out.println("queue.poll()"+queue.poll());
		System.out.println("queue.isEmpty: "+queue.isEmpty());
		
		
	}
}
